package com.googlecode.gaal.data.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.googlecode.gaal.data.api.Vector;

public class SparseVector implements Vector {
    private final List<Element> vector = new ArrayList<Element>();
    private double norm;

    @Override
    public void set(int x, int value) {
        Element element = new Element(x, value);
        double sumOfSquares = norm * norm;
        int index = Collections.binarySearch(vector, element);
        if (index < 0) {
            vector.add(-(index + 1), element);
        } else {
            int previous = vector.get(index).value;
            sumOfSquares -= previous * previous;
            vector.set(index, element);
        }
        norm = Math.sqrt(sumOfSquares + value * value);
    }

    @Override
    public void add(int x, int value) {
        Element element = new Element(x, value);
        double sumOfSquares = norm * norm;
        int index = Collections.binarySearch(vector, element);
        if (index < 0) {
            vector.add(-(index + 1), element);
        } else {
            int previous = vector.get(index).value;
            sumOfSquares -= previous * previous;
            element.value += previous;
            vector.set(index, element);
        }
        norm = Math.sqrt(sumOfSquares + element.value * element.value);
    }

    @Override
    public int get(int x) {
        Element element = new Element(x, 0);
        int index = Collections.binarySearch(vector, element);
        if (index < 0) {
            return 0;
        }
        return vector.get(index).value;
    }

    @Override
    public double norm() {
        return norm;
    }

    @Override
    public double similarity(Vector other) {
        return product(other) / (norm * other.norm());
    }

    @Override
    public double product(Vector otherVector) {
        if (otherVector instanceof SparseVector) {
            SparseVector other = (SparseVector) otherVector;
            double product = 0;
            for (int i = 0, j = 0; i < vector.size() && j < other.vector.size();) {
                if (vector.get(i).x < other.vector.get(j).x) {
                    i++;
                    continue;
                }
                if (vector.get(i).x > other.vector.get(j).x) {
                    j++;
                    continue;
                }
                product += vector.get(i).value * other.vector.get(j).value;
                i++;
                j++;
            }
            return product;
        } else {
            throw new UnsupportedOperationException();
        }
    }

    public static class Element implements Comparable<Element> {
        private final int x;
        private int value;

        public Element(int x, int value) {
            this.x = x;
            this.value = value;
        }

        @Override
        public int hashCode() {
            return x;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Element other = (Element) obj;
            if (x != other.x)
                return false;
            return true;
        }

        @Override
        public int compareTo(Element other) {
            return x - other.x;
        }

    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append('{');
        boolean isFirst = true;
        for (Element element : vector) {
            if (isFirst)
                isFirst = false;
            else
                builder.append(", ");
            builder.append(String.format("%d:%d", element.x, element.value));
        }
        builder.append('}');
        builder.append(String.format("(norm:%.2f)", norm));
        return builder.toString();
    }

    @Override
    public int size() {
        return vector.size();
    }
}
